{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question\n",
    "\n",
    "Discuss Towers of Hanoi puzzle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Answer\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use stack data structure here and I just use the one in [ToyData](https://github.com/shenxiangzhuang/ToyData). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-09-05T15:52:16.717718Z",
     "start_time": "2019-09-05T15:52:16.692554Z"
    }
   },
   "outputs": [],
   "source": [
    "class ArrayStack:\n",
    "    \"\"\"\n",
    "    LIFO Srtack implementation using Python list as underlyinh storage.\n",
    "    \"\"\"\n",
    "    def __init__(self):\n",
    "        \"\"\"Create and empty stack.\n",
    "        Space Complexity: O(n)\n",
    "        \"\"\"\n",
    "        self._data = []\n",
    "\n",
    "    def __len__(self):\n",
    "        \"\"\"Return the number of elements in the stack.\n",
    "        Time Complexity: O(1)\n",
    "        \"\"\"\n",
    "        return len(self._data)\n",
    "\n",
    "    def __str__(self):\n",
    "        \"\"\"\n",
    "        Show the stack properly.\n",
    "        Time Complexity: O(n)\n",
    "        \"\"\"\n",
    "        if self.is_empty():\n",
    "            s1 = '| ' + \"\".center(5) + ' |' + '\\n'\n",
    "            s2 = '-' * 9\n",
    "            return s1 + s2\n",
    "        else:\n",
    "            s = []\n",
    "            for i in range(len(self._data) - 1, -1, -1):\n",
    "                ele = self._data[i]\n",
    "                s1 = '| ' + ele.__repr__().center(5) + ' |' + '\\n'\n",
    "                s2 = '-' * 9 + '\\n'\n",
    "                s.append(s1 + s2)\n",
    "            return ''.join(s)\n",
    "\n",
    "    def is_empty(self):\n",
    "        \"\"\"Return True if the stack is empty\n",
    "        Time Complexity: O(1)\n",
    "        \"\"\"\n",
    "        return len(self._data) == 0\n",
    "\n",
    "    def push(self, e):\n",
    "        \"\"\"Add element to the top of the stack\n",
    "        Time Complexity: O(1)*\n",
    "        Note: \"*\" in here means amortization\n",
    "        \"\"\"\n",
    "        self._data.append(e)\n",
    "\n",
    "    def top(self):\n",
    "        \"\"\"\n",
    "        Return (but not remove) at the top of the stack.\n",
    "        Raise Empty exception if the stack in empty.\n",
    "        Time Complexity: O(1)\n",
    "        \"\"\"\n",
    "        if self.is_empty():\n",
    "            raise Empty(\"Stack in empty!\")\n",
    "        return self._data[-1]\n",
    "\n",
    "    def pop(self):\n",
    "        \"\"\"\n",
    "        Remove and return the element from the top of the stack(LIFO)\n",
    "        Raise Empty exception if the stack is empty.\n",
    "        Time Complexity: O(1)*\n",
    "        \"\"\"\n",
    "        if self.is_empty():\n",
    "            raise Empty(\"Stack is empty!\")\n",
    "        return self._data.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we get three towers(stacks)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-09-05T16:05:20.619963Z",
     "start_time": "2019-09-05T16:05:20.612538Z"
    }
   },
   "outputs": [],
   "source": [
    "stackA = ArrayStack()\n",
    "stackA.push(3)\n",
    "stackA.push(2)\n",
    "stackA.push(1)\n",
    "\n",
    "stackB = ArrayStack()\n",
    "stackC = ArrayStack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-09-05T16:05:21.040905Z",
     "start_time": "2019-09-05T16:05:21.035538Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|   1   |\n",
      "---------\n",
      "|   2   |\n",
      "---------\n",
      "|   3   |\n",
      "---------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(stackA)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-09-05T16:05:22.272884Z",
     "start_time": "2019-09-05T16:05:22.266649Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|       |\n",
      "---------\n"
     ]
    }
   ],
   "source": [
    "print(stackB)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-09-05T16:05:22.525156Z",
     "start_time": "2019-09-05T16:05:22.521003Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|       |\n",
      "---------\n"
     ]
    }
   ],
   "source": [
    "print(stackC)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And what we want to do is move the three disks in tower A to tower C, by tower B of course. Here for convenience, we give every tower a name."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-09-05T16:05:22.933708Z",
     "start_time": "2019-09-05T16:05:22.928849Z"
    }
   },
   "outputs": [],
   "source": [
    "stackA.name = 'A'\n",
    "stackB.name = 'B'\n",
    "stackC.name = 'C'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we go!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-09-05T16:05:23.683321Z",
     "start_time": "2019-09-05T16:05:23.674652Z"
    }
   },
   "outputs": [],
   "source": [
    "def move(start: ArrayStack, middle: ArrayStack, end: ArrayStack, n: int) -> None:\n",
    "    if n == 1:\n",
    "        ele = start.pop()\n",
    "        end.push(ele)\n",
    "        print(f\"move {ele} from {start.name} to {end.name}\")\n",
    "    else:\n",
    "        move(start, end, middle, n-1)\n",
    "        move(start, middle, end, 1)\n",
    "        move(middle, start, end,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-09-05T16:05:24.051749Z",
     "start_time": "2019-09-05T16:05:24.047922Z"
    }
   },
   "outputs": [],
   "source": [
    "def hanoi(start: ArrayStack, middle: ArrayStack, end: ArrayStack) -> None:\n",
    "    n = len(start)\n",
    "    move(start, middle, end, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-09-05T16:05:24.758973Z",
     "start_time": "2019-09-05T16:05:24.754680Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "move 1 from A to C\n",
      "move 2 from A to B\n",
      "move 1 from C to B\n",
      "move 3 from A to C\n",
      "move 1 from B to A\n",
      "move 2 from B to C\n",
      "move 1 from A to C\n"
     ]
    }
   ],
   "source": [
    "hanoi(stackA, stackB, stackC)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
